class Node {
  constructor(val) {
    this.val = val
    this.next = null
    this.prev = null
  }
}

class MyLinkedList {
  // 构造函数初始化虚拟头尾节点
  constructor() {
    this.head = new Node(null);
    this.tail = new Node(null);
    this.head.next = this.tail;
    this.tail.prev = this.head;
    this.size = 0;
  }

  addLast(e) {
    // if (e === null || e === undefined || e === '') {
    //   throw new Error('请传入实际值！')
    // }
    let x = new Node(e);
    let temp = this.tail.prev;
    // temp <-> tail  
    temp.next = x;
    x.prev = temp;

    x.next = this.tail;
    this.tail.prev = x;
    // temp <-> x <-> tail  
    this.size++;
  }

  addFirst(e) {
    let x = new Node(e);
    let temp = this.head.next;
    // head <-> temp  
    temp.prev = x;
    x.next = temp;

    this.head.next = x;
    x.prev = this.head;
    // head <-> x <-> temp  
    this.size++;
  }

  add(index, element) {
    this.checkPositionIndex(index);
    if (index === this.size) {
      this.addLast(element);
      return;
    }

    // 找到 index 对应的 Node  
    let p = this.getNode(index);
    let temp = p.prev;
    // temp <-> p  

    // 新要插入的 Node  
    let x = new Node(element);

    p.prev = x;
    temp.next = x;

    x.prev = temp;
    x.next = p;

    // temp <-> x <-> p  

    this.size++;
  }

  removeFirst() {
    if (this.size < 1) {
      throw new Error('NoSuchElementException');
    }
    // 虚拟节点的存在是我们不用考虑空指针的问题  
    let x = this.head.next;
    let temp = x.next;
    // head <-> x <-> temp  
    this.head.next = temp;
    temp.prev = this.head;

    x.prev = null;
    x.next = null;
    // head <-> temp  

    this.size--;
    return x.val;
  }

  removeLast() {
    if (this.size < 1) {
      throw new Error('NoSuchElementException');
    }
    let x = this.tail.prev;
    let temp = x.prev;
    // temp <-> x <-> tail  

    this.tail.prev = temp;
    temp.next = this.tail;

    x.prev = null;
    x.next = null;
    // temp <-> tail  

    this.size--;
    return x.val;
  }

  remove(index) {
    this.checkElementIndex(index);
    // 找到 index 对应的 Node  
    let x = this.getNode(index);
    let prev = x.prev;
    let next = x.next;
    // prev <-> x <-> next  
    prev.next = next;
    next.prev = prev;

    x.prev = x.next = null;
    // prev <-> next  

    this.size--;

    return x.val;
  }

  get(index) {
    this.checkElementIndex(index);
    // 找到 index 对应的 Node  
    let p = this.getNode(index);

    return p.val;
  }

  getFirst() {
    if (this.size < 1) {
      throw new Error('NoSuchElementException');
    }

    return this.head.next.val;
  }

  getLast() {
    if (this.size < 1) {
      throw new Error('NoSuchElementException');
    }

    return this.tail.prev.val;
  }

  set(index, val) {
    this.checkElementIndex(index);
    // 找到 index 对应的 Node  
    let p = this.getNode(index);

    let oldVal = p.val;
    p.val = val;

    return oldVal;
  }


  // 其他工具函数
  size() {
    return this.size;
  }

  isEmpty() {
    return this.size === 0;
  }

  isPositionIndex(index) {
    return index >= 0 && index <= this.size;
  }

  //  检查 index 索引位置是否可以添加元素
  checkPositionIndex(index) {
    if (!isPositionIndex(index))
      throw new Error("Index: " + index + ", Size: " + this.size);
  }

  isElementIndex(index) {
    return index >= 0 && index < this.size;
  }

  // 检查 index 索引位置是否可以存在元素
  checkElementIndex(index) {
    if (!isElementIndex(index))
      throw new Error("Index: " + index + ", Size: " + this.size);
  }

  getNode(index) {
    checkElementIndex(index);
    let p = this.head.next;
    // TODO: 可以优化，通过 index 判断从 head 还是 tail 开始遍历
    for (let i = 0; i < index; i++) {
      p = p.next;
    }
    return p;
  }

  display() {
    let arr = []
    for (let p = this.head.next; p !== this.tail; p = p.next) {
      arr.push(p.val)
    }
    console.log(arr.join('-->'));
  }
}

let doubleLinked = new MyLinkedList()

doubleLinked.addLast('')

doubleLinked.display()